package com.ds.bintree.LeetCode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author Dianzhi Han
 * @version 1.0
 * @description: 双形态标志法，若碰到第一个叶子结点或者第一个只有左子树没有右子树的结点进入第二形态
 * @date 2022/9/14 11:15
 */
public class Num958_IsCompleteTree {
    public boolean isCompleteTree(TreeNode root) {
        boolean second = false; //标志状态位，是否进入第二阶段
        Deque<TreeNode> queue = new LinkedList<>();
        if (root==null){
            return true;
        }
        if (root.right==null && root.left==null){
            return true;
        }
        if (root.left == null){
            return false;
        }
        queue.offer(root);
        while (!queue.isEmpty()){
            if (!second){ //第一阶段，一直往下层序遍历，找到第一个叶子结点或者度为1的结点
                TreeNode temp=queue.poll();
                if (temp.left==null && temp.right==null){
                    second=true;
                    continue;
                }
                if (temp.left!=null && temp.right==null){
                    second=true;
                    queue.offer(temp.left);
                    continue;
                }
                if (temp.left==null){
                    return false;
                }
                queue.offer(temp.left);
                queue.offer(temp.right);
            }else { //第二阶段只用判断接下来的结点是否都是叶子结点，若不是则不是完全二叉树
                TreeNode temp = queue.poll();
                if (temp.left!=null || temp.right!=null){
                    return false;
                }
            }
        }
        return true;
    }
}
